/**
 * https://leetcode.cn/submissions/detail/576995789/
 * 902. 最大为 N 的数字组合
 * Hard, 黄伟杰 2024.10.30
 * 数位DP
 */
#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int atMostNGivenDigitSet(vector<string> &digits, int n)
    {
        string s = to_string(n);
        int m = s.length(), dp[m];
        memset(dp, -1, sizeof(dp));
        auto dfs = [&](auto &&dfs, int i, bool is_limit, bool is_num) -> int
        {
            if (i == m)
            {
                return is_num; // is_num 为 true 表示得到了一个合法数字
            }
            if (!is_limit && is_num && dp[i] != -1)
            {
                return dp[i]; // 之前计算过
            }
            int res = 0;
            if (!is_num)
            { // 可以跳过当前数位
                res = dfs(dfs, i + 1, false, false);
            }
            // 上限
            char up = is_limit ? s[i] : '9';
            // 枚举要填入的数字 d
            for (auto &d : digits)
            {
                if (d[0] > up)
                    break;
                // is_limit现在受到约束，且等于上限，下一位也会受限制
                res += dfs(dfs, i + 1, is_limit && d[0] == up, true);
            }
            if (!is_limit && is_num)
            {
                dp[i] = res; // 记忆化
            }
            return res;
        };
        return dfs(dfs, 0, true, false);
    }
};